package com.hardy.gitchat;

import java.util.ArrayList;
import java.util.List;

/**
 * 贪心算法解决01背包问题
 *
 * @author fuxiaohui3@nuoyuan.com.cn
 * @date 2018/9/3 10:44
 */
public class Backpack01Problem {
    public static void main(String[] args) {
        ArrayList<Backpack> backpacks = initBackpacks();
        KnapsackProblem problem = new KnapsackProblem();
        problem.setObjs(backpacks);
        problem.setTotalC(150);
        GreedyAlgo(problem);


    }

    private static void GreedyAlgo(KnapsackProblem problem) {
        int idx;
        int ntc = 0;
        while ((idx = ChooseFunc2(problem.getObjs())) != -1) {
            if (ntc + problem.getObjs().get(idx).getWeight() <= problem.totalC) {
                problem.getObjs().get(idx).setStatus(1);
                ntc = ntc + problem.getObjs().get(idx).getWeight();
            } else {
                problem.getObjs().get(idx).setStatus(2);
            }
        }
        for (int i = 0; i < problem.getObjs().size(); i++) {
            if (problem.getObjs().get(i).getStatus() == 1) {
                System.out.println(problem.getObjs().get(i));
            }
        }
    }

    private static int ChooseFunc1(List<Backpack> backpacks) {
        int index = -1;
        int mp = 0;
        for (int i = 0; i < backpacks.size(); i++) {
            if (backpacks.get(i).getStatus() == 0 && backpacks.get(i).getPrice() > mp) {
                mp = backpacks.get(i).getPrice();
                index = i;
            }
        }
        System.out.println(index);
        return index;
    }

    private static int ChooseFunc2(List<Backpack> backpacks){
        int index = -1;
        int mp = 0;
        for (int i=0;i<backpacks.size();i++){
            if(backpacks.get(i).getStatus()==0 && backpacks.get(i).getPrice()/backpacks.get(i).getWeight()>mp){
                mp = backpacks.get(i).getPrice()/backpacks.get(i).getWeight();
                index =i;
            }
        }
        return index;
    }

    private static ArrayList<Backpack> initBackpacks() {
        ArrayList<Backpack> backpacks = new ArrayList<>();
        Backpack backpack1 = new Backpack(10, 35, 0);
        Backpack backpack2 = new Backpack(40, 30, 0);
        Backpack backpack3 = new Backpack(30, 60, 0);
        Backpack backpack4 = new Backpack(50, 50, 0);
        Backpack backpack5 = new Backpack(35, 40, 0);
        Backpack backpack6 = new Backpack(40, 10, 0);
        Backpack backpack7 = new Backpack(30, 25, 0);
        backpacks.add(backpack1);
        backpacks.add(backpack2);
        backpacks.add(backpack3);
        backpacks.add(backpack4);
        backpacks.add(backpack5);
        backpacks.add(backpack6);
        backpacks.add(backpack7);
        return backpacks;
    }

    static class KnapsackProblem {
        List<Backpack> objs;
        int totalC;

        public List<Backpack> getObjs() {
            return objs;
        }

        public void setObjs(List<Backpack> objs) {
            this.objs = objs;
        }

        public int getTotalC() {
            return totalC;
        }

        public void setTotalC(int totalC) {
            this.totalC = totalC;
        }
    }

    static class Backpack {
        /**
         * 价值
         */
        int price;
        /**
         * 重量
         */
        int weight;
        /**
         * 状态，0未选中，1选中，2已经被选中不可以选择了
         */
        int status;

        @Override
        public String toString() {
            return "Backpack{" +
                    "price=" + price +
                    ", weight=" + weight +
                    ", status=" + status +
                    '}';
        }

        public Backpack(int price, int weight, int status) {
            this.price = price;
            this.weight = weight;
            this.status = status;
        }

        public int getPrice() {
            return price;
        }

        public void setPrice(int price) {
            this.price = price;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }

        public int getStatus() {
            return status;
        }

        public void setStatus(int status) {
            this.status = status;
        }
    }
}
